package 经典排序算法;

import java.util.Scanner;

/**
 * @ClassName : 冒泡排序法
 * @Author : 骆发茂
 * @Date: 2021/3/4 9:19
 * @Description :
 * （1）原理：
 *
 * 1、从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
 * 2、指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
 * 3、依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
 * 4、依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
 * 5、重复上述过程，没排完一轮，比较次数就减少一次。
 * （2）例子：
 *
 * 待排序数据：7, 6, 9, 8, 5,1
 *
 * 第一轮排序过程：
 *
 * 指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1
 * 指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1
 * 指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1
 * 指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1
 * 指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9
 * 第一轮排序结束后，最大的数字9被移到了最右边。
 *
 * 进行第二轮排序，过程同上，只是由于最大的9已经放在最右边了，因此不用在比较9了，少了一次比较，第二轮结束的结果为：6,7,5,1,8,9
 *
 * 第三轮结果：6,5,1,7,8,9
 *
 * 第四轮比较结果：5,1,6,7,8,9
 *
 * 第五轮比较结果：1,5,6,7,8,9
 *
 * 最终排序结果为：1,5,6,7,8,9，由上可知N个数据排序，需要进行N-1轮排序；第i轮排序需要的比较次数为N-i次。
 *
 * （3）编码思路：
 *
 * 需要两层循环，第一层循环i表示排序的轮数，第二层循环j表示比较的次数。
 *
 * ---------------------------------------------------------------------------------------------------------------
 * 1、冒泡排序（Bubble Sort）
 * 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 *
 * 1.1 算法描述
 * 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 * 针对所有的元素重复以上的步骤，除了最后一个；
 * 重复步骤1~3，直到排序完成。
 *
 * 作者：SithCait
 * 链接：https://www.jianshu.com/p/c1efd6a8bb95
 * 来源：简书
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 冒泡排序法_数组按顺序两两交换 {

    public static void main(String[] args) {
        System.out.println("请输入一个串数字，以空格作为分割，我将为你排序");
        System.out.println("=================================");
        Scanner scanner = new Scanner(System.in);
        String strings = scanner.nextLine();
        String[] newstrings = strings.split(" ");
        int[] array = new int[newstrings.length];
        for (int i = 0; i < newstrings.length; i++) {
            array[i] = Integer.parseInt(newstrings[i]);
        }
        System.out.println("==========原数组排序前为：===============");
        for (int j : array) {
            System.out.print(j + "  ");
        }
        System.out.println();
        System.out.println("==========数组排序后为：===============");
        bubbleSort(array);
        for (int j : array) {
            System.out.print(j + "  ");
        }
        System.out.println();

    }


    public static int[] bubbleSort(int[] array) {
        if (array.length == 0) {
            return array;//null

        }
        for (int i = 0; i < array.length; i++) {//外层循环一次为一趟排序
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
}
